package 二分;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/4/10 11:21
 */
public class 美团前缀plus二分 {


    /*
     大致的 意思：
     给出一个数组 nums[],
     给出一个 查询的 次数  m
     这里简化一下, 直接 给出一个 查询的 数组 query[], 大小为 m

     query[i] 表示, 在 值 为 query[i] 的时候, 最多 能装 多少 nums[i] ^ 2
     ,
     按照lc 的风格直接 返回  query[i] 对应的 ans[] 数组
     */




    /*
     AC 了 ，其实很简单， 还是 二分  + 前缀和！
     */
    public int[] solution(int nums[],int query[]){
        int ans[] = new int[query.length];
        int []preSum  = new int[nums.length + 1];
        Arrays.sort(nums);
        // 前缀平方  ² 和
        for(int i = 0;i < nums.length ;i++){
            preSum[i + 1] = preSum[i] + nums[i] * nums[i];
        }
        int m = query.length,index = 0;
        while(index < m){
            int i = binarySearch(query[index],preSum);
            ans[index++] = i;
        }
        return ans;
    }

    private int binarySearch(int value,int preSum[]) {
        int l = 0,r = preSum.length - 1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(preSum[mid] > value){
                r = mid - 1;
            }else{
                l = mid;
            }
        }
        return l;
    }

    public int[] absoluteRightSolution(int nums[],int query[]){
        int ans[] = new int[query.length];
        Arrays.sort(nums);
        int m = query.length,index = 0;
        while(index < m){
            int sum = 0,count = 0;
            for(int i = 0;i < nums.length;i++){
                sum += nums[i] * nums[i];
                if(sum <= query[index]){
                    count++;
                }else{
                    break;
                }
            }
            ans[index++] = count;
        }
        return ans;
    }


    @Test
    public void test(){
        int testTimes = 5; // 自己写！
        int arraySize = 20;
        int max = 50;
        int min = 1;
        boolean fix = false;
        boolean isSuccess = true;
        for(int i = 0;i < testTimes;i++){
            int nums[] = ramdomArray(arraySize,max,min,fix);
            int query[] = ramdomArray(10,5000,min,fix);
            int[] ints = absoluteRightSolution(nums, query);
            int[] solution = solution(nums, query);
            System.out.println(Arrays.toString(ints));
            System.out.println(Arrays.toString(solution));

            if(!Arrays.equals(ints,solution)){
                isSuccess = false;
                System.out.println(Arrays.toString(ints));
            }
//            System.out.println(Arrays.toString(ints));
        }
        System.out.println(isSuccess ? " good" : "fuck!");
    }




    /**
     * 首先生成 随机数组的函数！
     *
     * @param arraySize 数组的大小（根据 题目的 不同， 也可能是 一个数组的  最大长度， 随机生成 数组的 长度 在 1 ~  arraySize 之间）
     * @param max       数组中元素的最大值
     * @param min       一个指标， 如果 min = 0， 代表 数组中的元素，>=0 ，min = 1， 代表 全是正数  min = -1 ，可正 ke 负 ， 可为 0
     * @param fix       如果 fix = true 代表， 数组的长度 固定， 反之， 数组的长度 不固定
     * @return 一个 生成的随机的数组(长度可以随机， 也可以 固定， 看具体题目的要求)
     */
    public int[] ramdomArray(int arraySize, int max, int min, boolean fix) {
        int ramdomArraySize = fix ? arraySize : (int) (Math.random() * (arraySize + 1)); // 数组的长度 , 由fix 来控制 是否随机
        int arr[] = new int[ramdomArraySize];
        if (min == 0) {
            for (int i = 0; i < ramdomArraySize; i++) {
                arr[i] = (int) (Math.random() * (max + 1)); // arr[i] = [0 , max]
            }
        } else if (min == 1) {
            for (int i = 0; i < ramdomArraySize; i++) {
                arr[i] = (int) (Math.random() * (max)) + 1;//  arr[i] =  [1 , max + 1)
            }
        } else {
            for (int i = 0; i < ramdomArraySize; i++) {
                arr[i] = (int) (Math.random() * (max + 1) - Math.random() * (max + 1)); // 可正 可 负 可为 0
            }
        }
        return arr;
    }


    public void testRight() {
        int testTimes = 100; // 自己写！
        int arraySize = 50;
        int max = 0;
        int min = 0;
        boolean fix = true;
        boolean isSuccess = true;
        for(int i = 0;i <  testTimes;i++){
            int[] ints = ramdomArray(arraySize, max, min, fix);
            int arr1[] = Arrays.copyOf(ints, ints.length);
            int arr2[] = Arrays.copyOf(ints, ints.length);
            // 你的方法
//            myFunction(arr1);
//            absoluteRightFunction(arr2);
            if(!Arrays.equals(arr1,arr2)){
                 /*
                  说明 有问题， 可以打印下，数组，看下是什么 问题！
                  */
                isSuccess = false;
                System.out.println(Arrays.toString(ints));
            }
        }
        System.out.println(isSuccess ? "success" : "fuck!");
    }


}
